/*
# File    :   make_prime.c
# Author  :   dongxicheng
# ref     :   http://dongxicheng.org/structure/prime/
*/

#include<stdio.h>

bool is_primer1(int num) 
{
    int i;
    for(i = 2; i < num; i++) {
        if(num % i == 0)  {
            return true;
        }
    }
    return false;
}



bool is_primer2(int num) {
    int i;
    int upper = sqrt(num);
    printf("primer2:%d\n", upper);
    for(i = 2; i <= upper; i++) {
        if(num % i == 0) {
            return true;
        }
    }
    return false;
}


bool load_primer_table1() { //保存素数表
    int i;
    for(i = 1; i < INT_MAX; i++) {
        if(i % 2 != 0 //偶数一定不是素数
           && is_primer2(i)) {
            set(i);
        }
    }
}

bool load_primer_table2() {//另一种更快的方法保存素数表
    int i, j;
    for(i = 1; i <= INT_MAX; i++) { 
        if( i % 2) { 
            set(i); 
        } else {
            clear(i);
        }
    }
    int upper = sqrt(INT_MAX);
    for(i = 1; i <= upper; i++) {
        if(test(i)) {
            for(j = i + i; j < INT_MAX; j += i)
                set(i);
        }
    }
}

bool is_primer3(long num) { //查表判断是否为素数
    if(test(num))
        return true;
    return false;
}





5. 优化的筛选算法

(1) 存储方式优化

仍然采用位图方式存储，只不过是位图中只存储奇数，这样一下子节省了一半空间（需要的空间仅为4G/(32*2)=64MB）

存储空间优化后，算法效率也会提升很多，如：1,2，…,30

只需存储3,5,7,9,11,13,15,17,19,21,23,25,27,29

i=0, is_primer[0] =true, 把下标[3][6][9][12]，即9,15,21,27,标为false

i=1, s_primer[0] =true,把下标为[6][11],即15,25标为false

i=2, 2*i+3>sqrt(30),结束

即：i=s, 把下标为s(2*t+1)+3t,其中，t=1,2,3，…中所有的的is_primer置为false

(2) 优化删选算法

a是素数，则下一个起点是a*a,把后面的所有的a*a+2*i*a筛掉。即欲求n以内的素数，就先把sqrt(n)内的素数求出来，用已经求得的素数来筛出后面的合数。
